/*报告3：利用栈的原理完成中缀表达式转后缀表达式*/
#include <stdio.h>
#include <stdlib.h>

#define INITSTACK(s) s = (ST)malloc(sizeof(Stack))
#define FREESTACK(s) free((void *)s)

typedef int Elem;
typedef struct Stack{ 	//定义栈结构体
	Elem *elem;
	int n; 	//栈容量
	int top;	 //栈顶指针下标，默认为-1，空栈;0表示有1个元素
}Stack, *ST;

/*函数声明列表*/
int CreateStack(ST s, int n);	 //建栈	done
int CreateStack_Plus();	 //建站2.0,可自定义栈元素数据类型
/*Question:
 1. 不同结构体，必须用不同结构体指针？(不同数据类型的栈分开定义)
 2. 按照多位操作数的解决方法，计算结果产生double型，如何入OPND栈？
 3. 栈的初始化与创建：
 		通过结构体指针初始化，需要在main()中调用malloc()申请空间
		可否通过一个函数，一步实现初始化与创建？
		可否通过一个函数，对不同数据元素类型的栈进行创建？
*/

void ClearStack(ST s);	//销毁栈	done

int Push(ST s, Elem e); 	//入栈	done
int Pop(ST s, Elem e);	 //出栈		done

int Calculate(); 	//中缀表达式计算

Elem GetTop(ST s); 	//读取栈顶元素(不取出)  done

int InStackComp(Elem);	 //栈内优先级计算
int OutStackComp(Elem); 	//栈外优先级计算

int Compute(int m, char c, int n); 	//计算，暂定结果仍然为int型

//操作符判断,1真0假   
int IsOp(){
	;
}
/*未完成，难点： 	1.+、-做一元、二元运算符的分辨
							   	2.形参类型，char(多位数；个位数int->char，丢位？) or int(操作符)
					多位操作数：科学计数按位求幂，再求和
					一元操作符：左侧检测：无 or 左括号
*/

/*main()*/
int main(){
	ST s1; 	INITSTACK(s1);
	int t1, t2;
	t1 = CreateStack(s1, 5);
	switch(t1){
		case -1: printf("栈空间申请失败\n");
		case 1: printf("建栈成功\n");
	}
	//测试代码

	ClearStack(s1); 	FREESTACK(s1); ;
	return 0;	
}


/*函数定义列表*/
int CreateStack(ST s, int n){
	if(n <= 0) 	return 0; 	//返回0,空栈
	s->top = -1; 	s->n = n;
	s->elem = (Elem *)malloc(sizeof(Elem) * n);
	if(s->elem == NULL) 	return -1; 	//返回-1，栈元素空间申请失败;
	return 1;
}

void ClearStack(ST s){
	s->n = 0;	 s->top = -1;
	free((void *)s->elem);
	printf("栈空间清理完毕\n");
}

int Push(ST s, Elem e){
	if(s->top >= (s->n - 1))	 return 0; 	//返回0,栈满
	s->elem[++s->top] = e;
	return 1;
}

int Pop(ST s, Elem e){
	if(s->top == -1) 	return 0; 	//返回0.空栈
	e = s->elem[s->top--];
	return 1;
}

Elem GetTop(ST s){
	return s->elem[s->top];
}

int Calculate(){
	ST OPTR, OPND;
	INITSTACK(OPTR);	INITSTACK(OPND);
	CreatteStack(OPTR);	CreateStack(OPND); 	//初始化、创建符号栈OPTR、操作数栈OPND
	Push(OPTR, '#');
	char a, b;
	int i, j, n, m;
	int res; 	//暂定Compute计算结果为int型

	a = getchar();
	while(a != '#' || GetTop(OPTR) != '#'){
		if(!IsOp(a)) 	Push(OPND, a);	
		else{
			b = GetTop(OPTR);
			i = OutStackComp(a); 	j = InStackComp(b);
			if(i < j) 	Push(OPTR, a);
			else{
				Pop(OPTR, b);
				if(b != '(')
				Pop(OPND, n); 	Pop(OPND, m);	 //读取操作数，栈结构决定为(m ? n)格式
				Push(OPND, Compute(m, a, n));
				//出现question中的若干问题，暂时无法使用Push()直接解决，暂定结果为int
			}
		}
		a = getchar();
	}

	Pop(OPND, res);
	return res;
}
